package cn.guo.algorithm.sort.exchange;

import cn.guo.algorithm.AlgorithmUtils;

import java.util.List;

/**
 * TODO:快速排序 快排的时间复杂度为:平均复杂度： N(logN); 最坏复杂度：0(n^2)
 * [20,40,50,10,60]
 * left指针，right指针，base参照数。

 * 其实思想是蛮简单的，就是通过第一遍的遍历（让left和right指针重合）来找到数组的切割点。

 * 第一步：首先我们从数组的left位置取出该数（20）作为基准（base）参照物。
 *
 * 第二步：从数组的right位置向前找，一直找到比（base）小的数，
 * 如果找到，将此数赋给left位置（也就是将10赋给20），
 * 此时数组为：10，40，50，10，60，
 * left和right指针分别为前后的10。
 *
 * 第三步：从数组的left位置向后找，一直找到比（base）大的数，
 * 如果找到，将此数赋给right的位置（也就是40赋给10），
 * 此时数组为：10，40，50，40，60，
 * left和right指针分别为前后的40。
 *
 * 第四步：重复“第二,第三“步骤，直到left和right指针重合，
 * 最后将（base）插入到40的位置，
 * 此时数组值为： 10，20，50，40，60，至此完成一次排序。
 *
 * 第五步：此时20已经潜入到数组的内部，20的左侧一组数都比20小，20的右侧作为一组数都比20大，
 * 以20为切入点对左右两边数按照"第一，第二，第三，第四"步骤进行，最终快排大功告成。
 * <p/>
 * Created by guo on 2015/10/19.
 */
public class QuickSort {

    public static void main(String[] args) {
        //产生随机数组
        int length = 1000;
        long a = System.currentTimeMillis();
        List<Integer> arr = AlgorithmUtils.getRandomList2(length);
        AlgorithmUtils.asyncPrintArrayList(arr);
        long b = System.currentTimeMillis();
        AlgorithmUtils.asyncPrintMsg("生成[" + length + "]个不等随机数耗时[" + (b - a) + "]ms");
        //对随机数进行
        QuickSoredList(arr, 0, arr.size() - 1);
        AlgorithmUtils.asyncPrintArrayList(arr);
        long c = System.currentTimeMillis();
        AlgorithmUtils.asyncPrintMsg("快速排序大小为[" + length + "]的数组,耗时[" + (c - b) + "]ms");
    }

    private static void QuickSoredList(List<Integer> arr, int left, int right) {
        if (left < right) {
            int division = getDivision(arr, left, right);
            //左侧排序
            QuickSoredList(arr, left, division - 1);
            //右侧排序
            QuickSoredList(arr, division + 1, right);
        }
    }

    /**
     * 获取下次分割的基准脚标
     *
     * @param arr
     * @param left
     * @param right
     * @return
     */
    private static int getDivision(List<Integer> arr, int left, int right) {
        int base = arr.get(left);
        while (left < right) {
            //直到right找到比base小或者相等的数
            while (left < right && arr.get(right) >= base) {
                right -= 1;
            }
            arr.set(left, arr.get(right));
            //直到left找到比base大或者相等的数
            while (left < right && arr.get(left) <= base) {
                left += 1;
            }
            arr.set(right, arr.get(left));
        }
        arr.set(left, base);
        return left;
    }

}
